<head>
    <meta charset="UTF-8">
<title>算法提高 Tunnels</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>【问题描述】</p>
<p>一个间谍从你的陷阱中逃出来了，干掉了你的警卫，并且带走了你毁灭世界的计划。你的糟糕的行动由此受到了威胁。现在你需要在他逃出基地之前抓到他。</p>
<p>你的基地由一系列房间和连接它们的双向隧道组成，隧道只在房间处相交。每个房间都配有监控摄像，使你能在任意时刻了解间谍所处的位置。另外，每条隧道里都装有遥控炸药，触发后可以永久毁坏该隧道。间谍在隧道中移动极快，因此你不可能把他困在炸毁的一条隧道中，但你可以炸毁一些隧道，使他无法逃出基地。&nbsp;</p>
<div>显然，间谍不可能逃出基地。所以你的目标是在困住他的同时炸毁最少的隧道，因为之后的重建非常昂贵。找到一种策略，使得在最坏情况下需要炸毁的隧道数最小。</div>
<div>&nbsp;</div>
<p>【输入格式】</p>
<p>&nbsp;输入包含多组数据。每组数据的第一行包含两个整数R, T，分别表示房间的隧道的数量。接下来T行，每行两个整数a, b(0 &lt;= a, b &lt;= R)，表示隧道两端的房间编号。形如&quot;0 x&quot;或&quot;x 0&quot;的输入表示联通房间x和基地外部的隧道。</p>
<p>间谍从1出发，你需要阻止他到达点0（基地外部）。</p>
<p>【输出格式】</p>
<p>对第i组输入，输出&quot;Case $i: ${ans}\n\n&quot;，其中${ans}表示对应的答案。</p>
<p>参见样例输出的格式。</p>
<p>【样例输入】</p>
<p>4 6</p>
<p>1 2</p>
<p>1 3</p>
<p>2 4</p>
<p>3 4</p>
<p>4 0</p>
<p>4 0</p>
<p>4 6</p>
<p>1 2</p>
<p>1 3</p>
<p>1 4</p>
<p>2 0</p>
<p>3 0</p>
<p>4 0</p>
<p>0 0</p>
<p>&nbsp;</p>
<p>【样例输出】</p>
<p>Case 1: 2</p>
<p>&nbsp;</p>
<p>Case 2: 2</p>
<p>&nbsp;</p>
<p><span style="color: rgb(255, 255, 255);">如你所见, 输出的最后有一个空行。</span></p>
<p>【数据规模和约定】<br class="Apple-interchange-newline" />
1 &lt;= R &lt;= 50, 1 &lt;= T &lt;= 1000。</p>
<div>每个测试点至多包含五组数据。</div>
<p>&nbsp;</p>